約 221,383 件
https://w.atwiki.jp/akitaicpc/pages/36.html
C言語における文字列の扱い C言語には、C++やJavaと違い文字列型(string型)は存在しません。 文字列はchar型の配列として表現されます。そのため、ライブラリ(主にstring.h)を使わないと 文字列処理ができないので関数リファレンスが手元にあると便利です。 文字列の宣言 cahr str[80] = "hoge"; 文字列を逆にする関数 /* *reverse_string.c *by otaks , 2011-01-14 */ #include stdio.h #include string.h //引数strを逆にしてstrに代入する関数 void reverseString(char *str){ int length = strlen(str), i; char temp; for(i=0 ; i length/2 ; i++){ temp = str[length-i-1]; str[length-i-1] = str[i]; str[i] = temp; } } int main(){ char str[80]; printf("文字列を入力してください "); scanf("%s" , str); reverseString(str); printf("%s \n", str); return 0; } C++であれば alrogithm をインクルードすればreverse()という関数が使えるので実装する必要がなくなります。 /* *reverse_string.cpp *by otaks , 2011-01-14 */ #include iostream #include string #include algorithm using namespace std; int main(){ string s; while( cin s , str!="quit" ){ reverse( s.begin() , s.end() ); cout "output " str endl; } } 文字列処理に関する関数 string.h で定義されている文字列処理の関数には、文字数を指定するものがあります。こっちを使った方が安全性が高いです。理由は、自分で作ってみればわかります。例えば、 strlen を自作するなら、 size_t myStrlen(char *s){ int i; for(i = 0; s[i] != \0 ; ++i); return (size_t)i; } こんな感じに実装できると思います。よく考えてください。もし配列上に \0 のものがなければ、配列の領域を超えてアクセスしてしまうことになります。なので、配列の長さを受け取って、 size_t myStrnlen(char *s, size_t len){ int i; for(i = 0; s[i] != \0 i len; ++i); return (size_t)i; } こうすることで配列の長さを超えてアクセスしてしまうということがなくなります。だから、 strlen を使うより strnlen を使う方が安全なのです。まあ ACM ではそんなことは関係ねー、そんなの関係ねー。 ...
https://w.atwiki.jp/akitaicpc/pages/89.html
探索アルゴリズム 基本的な探索アルゴリズム 深さ優先探索 DFS? 幅優先探索 BFS? 二分探索? 枝刈り探索? ...
https://w.atwiki.jp/akitaicpc/pages/94.html
配列を逆順にする 配列を逆順にしたい時は、次のようにするとよいでしょう。( algorithm ヘッダをインクルードするのを忘れずに!) void reverseArray(int a[], int n){ for(int i=0 ; i n/2 ; i++) swap( a[i] , a[n-i-1] ); } 実はC++の algprithm ヘッダにはreverse()関数があるので文字列や配列などを逆順にする関数を自分で作る必要はありません。 例えばvector int vc;に対して逆順にしたいなら reverse( vc.begin() , vc.end() ); とするだけで逆順になります。 std stringも逆順にできるので文字列を逆順にするのも簡単です。 ...
https://w.atwiki.jp/akitaicpc/pages/40.html
エラトステネスのふるい(素数判定) 素数表を生成するアルゴリズムにエラトステネスのふるいというものがあります。 まずはこのアルゴリズムなしで素数かどうか調べる方法を考えてみます。 ある数が素数かどうか調べるにはその数がその数より小さい数すべて(1以外)で 割り切れない場合素数なのでfor文で回せば簡単にコーディングできそうです。 +プログラム例 /*入力した値が素数かどうか識別するプログラム*/ #include iostream using namespace std; int main(){ int n; while( cin n , n ){ bool flag = true; //1は素数でない if( n == 1 ) flag = false; //nを2から(n-1)まで割って割り切れるか調べる for (int i=2 ; i n ; i++ ){ if ( n % i == 0 ){ //割り切れたら素数でない flag = false; break; } } if( flag ) cout "数値は素数です" endl; else cout "数値は素数ではありません" endl; } } この方法では大きな数に対して素数判定をすると非常に時間がかかります。 エラトステネスのふるいという方法は先程よりも効率がよく10^6程度の数であれば高速に素数判定ができます。 wikidediaのエラトステネスの篩に詳しい説明があるのでここでは説明しません。 以下がプログラム例です。 /*1000000以下の素数で入力したn以下の素数をすべて出力するプログラム*/ #include iostream #include cmath const int MAX = 1000001; using namespace std; bool p[MAX]; void sieve_of_eratosthenes(){ for(int i=0 ; i MAX ; i++){ p[i] = (i =1)? false true ; } for(int i=2 ; i = sqrt(MAX)+1 ; i++){ if( p[i] ){ for(int j=i*2 ; j MAX ; j+=i){ p[j] = false; } } } } int main(){ int n; sieve_of_eratosthenes(); while( cin n , n ){ for(int i=n ; i 0 ; i--){ if( p[i] ){ cout i endl; } } } } ...
https://w.atwiki.jp/akitaicpc/pages/28.html
スタック・キュー (画像などを入れて解説してくれると助かります。私はうまいこと画像を用意できませんorz あと、読みづらいところ、間違ってるところあったらバッサリ書き換えちゃっていいですよ。) スタック スタック (stack) とはデータ構造の一つです。スタックにデータを追加することをプッシュ (push) と言い、スタックからデータを取り出すことをポップ (pop) と言います。後にプッシュしたデータほど先にポップされるという特徴があります。これを Last In, First Out (LIFO) といいます。 イメージとしては、筒を思い浮かべるとわかりやすいと思います。ここでいう筒とは、有限長の円柱や多角柱の一方の端に、その角柱の断面と同形状の壁がついているもののことをいいます。筒の開いている端から物を入れていくと、先に入れた物ほど後で取り出せ、後に入れた物ほど先に取り出せるのがわかると思います。 なお、スタックは C++ の STL ですでに実装されています。 STL のスタックを使うときは、 #include stack でクラステンプレートを読み込み、 std stack データ型 スタック変数名 で実際にスタックを使います。 プッシュは スタック変数名.push(データ) 一番上のデータを調べるときは スタック変数名.top() ポップは スタック変数名.pop() です。 キュー キュー (queue) もデータ構造の一つです。キューにデータを追加することをエンキュー (enqueue) と言い、キューからデータを取り出すことをデキュー (dequeue) と言います。先にエンキューしたデータほど先にデキューされるという特徴があります。これを First In, First Out (FIFO) と言います。 イメージとしては、レジの待ち行列を思い浮かべるとわかりやすいと思います。順番に並んでいて、先に並んだ人が先にレジのサービスを受けられるのがわかると思います。(横入りなどはないものとします) なお、キューは C++ の STL で実装されています。STL のキューを使うときは、 #include queue でクラステンプレートを読み込み。 std queue データ型 キュー変数名 で実際にキューを使います。 STL のキューはメソッド名がスタックと同じで、push でエンキュー、pop でデキューとなっています。 キュー変数名.push(データ)// エンキュー キュー変数名.pop()// デキュー また、先頭のデータ (デキューすると取り出されるデータ) を返すメソッドは front() で、末尾のデータ (直前にエンキューされたデータ) を返すメソッドは back() です。 キュー変数名.front()// 直前にエンキューされたデータ キュー変数名.back()// デキューすると取り出されるデータ ...
https://w.atwiki.jp/akitaicpc/pages/23.html
ハノイの塔 ...
https://w.atwiki.jp/akitaicpc/pages/85.html
木構造
https://w.atwiki.jp/akitaicpc/pages/26.html
練習用ページ ここはwikiの編集になれるためにつくったページです。 自由に編集してもOKです! スペースを入れると文字全体の背景色が変わります 大見出し 中見出し 小見出し 太字 下線付き文字 リスト1 リスト2 リスト3 番号リスト 番号リスト 番号リスト テーブルは 縦棒で くぎります 何か1 何か2 何か3 半角 で始めると引用文になります。 +... 折りたたみその1 あああああああ いいいいいいい -説明 折りたたみその2 あああああああ いいいいいいい +説明 折りたたみその3 あああああああ いいいいいいい +ショートコーダへの道 ここに何か書いてね!
https://w.atwiki.jp/akitaicpc/pages/16.html
Linuxでよく使うコマンド -説明 Linuxでよく使うコマンドを書いています。必要最低限の説明しか載せていないので 詳細は各自調べてください。 説明が2行以上のときは+を押して読んでください。 Linuxではコンソール上でコマンドを使っていろいろな操作を行います。 コンソール上で コマンド名 [オプション] [ファイル名・ディレクトリ名] と入力します。オプションは-o,-iなどたくさんありますが省略可能です。 ファイル名・ディレクトリ名の指定が不要のコマンドもあります。 またファイル名・ディレクトリ名を複数指定できるコマンドもあります。 pwd カレントディレクトリの表示 ls ディレクトリの表示 +説明 ls -aと入力すると普段は表示されないファイルもすべて表示されます。 date 今日の日付・時間の表示 cal カレンダーの表示 cd ホームフォルダに移動 cd ディレクトリ名1 ディレクトリ名1に移動 cd ../ 一つ上の階層に移動 cat ファイル名1 ファイル名1の内容を表示 +説明 cat a.txt と入力するとa.txtの内容がコンソール上に表示されます cp ファイル名1 ファイル名2 ファイル名1をファイル名2にコピーする +説明 ファイル名2が存在すると上書きされます。 cp ファイル名1 ディレクトリ名1/ファイル名2 ファイル名1をディレクトリ名1の中のファイル名2にコピーする cp -r ディレクトリ名1 ディレクトリ名2 ディレクトリ名1に含まれるファイルすべてをディレクトリ名2にコピーする cp ディレクトリ名1/ファイル名1 . ディレクトリ名1の中のファイル名1をカレントディレクトリにコピーする +説明 3つめの引数の . がカレントディレクトリを表しています。 cp ディレクトリ名1/* . ディレクトリ名1の中のすべてのファイルをカレントディレクトリにコピーする +説明 *はワイルドカードと言い、特殊な意味を持つ記号列です。 2番目をディレクトリ名/*.txtとするとファイル名の末尾が.txtとなっている ファイル(テキストファイル)すべてをカレントディレクトリにコピーします。 mv ファイル名1 ファイル名2 ファイル名1をファイル名2に名称変更 mv ファイル名1 ディレクトリ名1 ファイル名1をディレクトリ名1に移動 +説明 mvコマンドはcpコマンドと使い方がほとんど一緒です。 mvとcpの違いは、mvはファイルを移動した後、元あったファイルは消えるが cpはのこるため2つにファイルが増えます。 rm ファイル名1 ファイル名1を削除する rm ファイル名1 ファイル名2 ファイル名3 ファイル名1~3を削除する +説明 rmコマンドはファイル名を半角スペースで区切れば複数指定できます。 また rm *.txt と入力すれば拡張子が.txtのものをすべて削除できます。 cp - CoPy mv - MoVe rm - ReMove rmdir ディレクトリ名1 ディレクトリ名1を削除する(ディレクトリ名1が空でないと削除できない) rm -r ディレクトリ名1 ディレクトリ名1を削除する xemacs ファイル名1 ファイル名1をxemacs(エディタ)で起動する +説明 ファイル名1が存在しない場合には新規作成されます。 コマンドの最後に と追加することによりバッググラウンドでxemacsを動かすことができます。 バッググラウンドで動かすとxemacsで編集しつつ、コンソールで並行して操作できます。 xemacsの使い方はここでは説明しません。 vi ファイル名1 ファイル名1をvi(エディタ)で起動する cc ファイル名1.c g++ ファイル名1.cpp ファイル名1をコンパイルする +説明 ccコマンドでC言語のソースファイルをコンパイルできます。 g++コマンドでC++言語のソースファイルをコンパイルできます。 ソースファイルに間違いがあるとコンパイルエラーが出ます。 コンパイルに成功するとa.outというファイル名のオブジェクトファイルが生成されます。 cc -o ファイル名.exe ファイル名.c g++ -o ファイル名.exe ファイル名.cpp +説明 -o オプションを付けることで生成されるファイルの名前を指定できます。 ファイルの名前は何でもいいのですが、 実行可能ファイルなので拡張子は.exeにした方がいいでしょう。 ./実行したいファイル名 コンパイルしてできたファイルを実行するにはファイル名の前に./とつける必要があります。 man コマンド名 コマンド名のマニュアルを表示する ...
https://w.atwiki.jp/akitaicpc/pages/95.html
配列を巡回シフトさせる 例えば、配列aが a[5] = {0,1,2,3,4} となっているところを a[5] = {2,3,4,0,1} のように巡回シフトさせたいことがあるかもしれません。 そんなときは次の関数を使うとよいでしょう。 //配列aの要素を右にj個巡回シフトする void rotArray(int a[], int n, int j){ int *temp = new int[n]; while(j 0) j+=n; for(int i=0 ; i n ; i++){ temp[(i+j)%n] = a[i]; } for(int i=0 ; i n ; i++){ a[i] = temp[i]; } delete [] temp; } jを-1とすれば左に1個分巡回シフトします。 この関数は、一時変数tempを使っているので無駄があります。 もし、あなたがこの関数をよりよいアルゴリズムに改良できたならこのページを編集しましょう。 ...